package cn.njupt.map;

public class LinkedHashMap<K,V> extends HashMap<K,V>{

    private LinkedNode<K,V> first;
    private LinkedNode<K,V> last;


    protected static class LinkedNode<K,V> extends Node<K,V>{
        LinkedNode<K,V> prev;
        LinkedNode<K,V> next;
        public LinkedNode(K key, V value, Node<K, V> parent) {
            super(key, value, parent);
        }
    }


    @Override
    protected Node<K, V> createNode(K key, V value, Node<K, V> parent) {
        LinkedNode<K,V> newNode=new LinkedNode<>(key,value,parent);
        if(first==null){
            first=newNode;
            last=newNode;
        }else{
            last.next=newNode;
            newNode.prev=last;
            last=newNode;
        }
        return newNode;
    }

    @Override
    public void clear() {
        super.clear();
        first=null;
        last=null;
    }

    @Override
    public void traversal(Visitor<K, V> visitor) {
        if(visitor==null)return;
        LinkedNode<K,V> node=first;
        while(node!=null){
            if(visitor.visitor(node.key,node.value))return;
            node=node.next;
        }
    }

    @Override
    protected void afterRemove(Node<K,V> willNode,Node<K, V> removeNode) {
        //说明删除的节点有左右子树，用后继节点替换的根节点
        LinkedNode<K,V> node1=(LinkedNode<K, V>) willNode;
        LinkedNode<K,V> node2=(LinkedNode<K, V>) removeNode;
        if(willNode!=removeNode){
//         在链表中交换willNode和removeNode
           LinkedNode<K,V> temp=node1.prev;
           node1.prev=node2.prev;
           node2.prev=temp;

           if(node1.prev==null){
               first=node1;
           }else{
               node1.prev.next=node1;
           }
           if(node2.prev==null){
               first=node2;
           }else{
               node2.prev.next=node2;
           }

           temp=node1.next;
           node1.next=node2.next;
           node2.next=temp;
           if(node1.next==null){
               last=node1;
           }else{
               node1.next.prev=node1;
           }
            if(node2.next==null){
                last=node2;
            }else{
                node2.next.prev=node2;
            }
        }

//      从链表中删除node节点
        LinkedNode<K,V> prev=node2.prev;
        LinkedNode<K,V> next=node2.next;

        //说明是首节点
        if(prev==null){
            first=next;
        }else{
            prev.next=next;
        }

        //说明尾结点
        if(next==null){
            last=prev;
        }else{
            next.prev=prev;
        }


    }

}
